首页 > 试题广场 >

字符串出现次数的TopK问题

[编程题]字符串出现次数的TopK问题
  • 热度指数:44027 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串数组,再给定整数 k ,请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率,按字典序排序。
对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb","231"<”32“
字符仅包含数字和字母

数据范围:字符串数满足 ,每个字符串长度
要求:空间复杂度 ,时间复杂度

示例1

输入

["a","b","c","b"],2

输出

[["b","2"],["a","1"]]

说明

"b"出现了2次,记["b","2"],"a"与"c"各出现1次,但是a字典序在c前面,记["a","1"],最后返回[["b","2"],["a","1"]]
   
示例2

输入

["123","123","231","32"],2

输出

[["123","2"],["231","1"]]

说明

 "123"出现了2次,记["123","2"],"231"与"32"各出现1次,但是"231"字典序在"32"前面,记["231","1"],最后返回[["123","2"],["231","1"]]   
示例3

输入

["abcd","abcd","abcd","pwb2","abcd","pwb2","p12"],3

输出

[["abcd","4"],["pwb2","2"],["p12","1"]]

备注:
function topKstrings( strings ,  k ) {
    // write code here
    const map = new Map()
    strings.forEach((item) => {
        if (map.has(item)) map.set(item, map.get(item) + 1)
        else map.set(item, 1)
    })
    return [...map].sort((a, b) => {
        if (a[1] === b[1]) {
            if (a[0] > b[0]) return 1
            else return -1
        } else return b[1] - a[1]
    }).slice(0, k)
}

发表于 2021-11-19 15:38:02 回复(0)
function topKstrings( strings ,  k ) {
    // write code here
    strings.sort();
    let ans = [];
    for(let i = 0 ; i < strings.length;){
        let j = i+1;
        while(j<strings.length&&strings[j]===strings[i]){j++;}
        ans.push([strings[i],(j-i).toString()]);
        i = j;
    }
    ans.sort((a,b)=>b[1]-a[1])
    return ans.slice(0,k);
}

发表于 2021-09-13 13:59:11 回复(0)